#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
int grid[10][10];				//grid
int next_grid_snap[10][10];			// next grid snap to check connectivity
int basestation;				//
int admatrix[26][26];				// adjacency matrix for node connectivity
int gridwithbotno[10][10];			// for numbering nodes
int bot[26];			
int visited[10][10];				// to take into account which cell is visited how many times

void movebots();				// to move bots in sequence order
int chkconnectivity();				// for checking connectivity...it calls connected(basestation)  
void connected(int startpoint);			// 
void createadjacencylist();			// for creating adjacency matrix
void numberbots();				// numbering bots to create adjacency matrix
void initializebotpositions();
void chkneighbours(int i , int j , int botnum);
int get_cells_to_move(int i , int j);
void print();
void movetonewposition(int position , int i , int j);
void printnext();
void printnumberedbot();
void printad();
void initializegridbot();
void clearadjacencymatrix();
void initialize_visited_matrix();
void printvisited();

int main()
{
        srand(time(NULL));
	initializebotpositions();
	initialize_visited_matrix();
	movebots();
	
return 0;
}

void movebots()
{
	basestation = gridwithbotno[5][4];
	int bot_to_move=0;
	int i,j;
	int k;
	int i_bp,j_bp;
	int bot_position ;
	int count =0;
	
                //printvisited();	
		while(count != 1000 )	
		{	
				
			//print();
			numberbots();  
			//printnumberedbot();
			bot_to_move = rand()%26 + 1;
                        /*bot_to_move++;                        
			if(bot_to_move==27)
                        	bot_to_move=1;*/
			//printf("Bot to move %d\n",bot_to_move);
			for(i =0 ; i<10 ; i++)
			{
				for(j=0 ; j<10 ; j++)
				{
					if (gridwithbotno[i][j] == bot_to_move)
					{
						i_bp = i ; j_bp = j ;
						break;
					}
				}
			}
			
			if(!(i_bp ==5 && j_bp == 4))
			{
				//printf("Bot's Position : i = %d  j = %d\n",i_bp ,j_bp );
				bot_position = get_cells_to_move(i_bp,j_bp);	
				//printf("Next Movement to postion: %d\n",bot_position);
				if(bot_position != 0 )
				{
					movetonewposition(bot_position, i_bp , j_bp);
				}else{
					int rand_position = rand()%8+1 ;
					movetonewposition(rand_position, i_bp , j_bp);
					}			
			}
			count++;
                        //printvisited();   
			//sleep(1);
			//system("clear") ;
			//printf("\n\n===========================================================================\n\n");
		}
		//printvisited();	
}

int get_cells_to_move(int i , int j)
{
	int p_position =0 ;
	
	if((i-1)>=0 && (j-1)>=0 && (visited[i-1][j-1] == 0))
	{
		p_position=1; 
	}else if ((i-1)>=0 && (j)>=0 && (visited[i-1][j] == 0))
	{
		p_position=2; 
	}else if((i-1)>=0 && (j+1)< 10 && (visited[i-1][j+1] == 0))
	{
		p_position=3; 
	}else if((i)>=0 && (j+1)<10 && (visited[i][j+1] == 0))
	{
		p_position=4;
	}else if((i+1)<10 && (j+1)<10 && (visited[i+1][j+1] == 0))
	{
		p_position=5;
	}else if((i+1)<10 && (j)>=0 && (visited[i+1][j] == 0))
	{
		p_position=6;
	}else if((i+1)<10 && (j-1)>=0 && (visited[i+1][j-1] == 0))
	{
		p_position=7; 
	}else if((i)>=0 && (j-1)>=0 && (visited[i][j-1] == 0))
	{
		p_position=8;
	}
	
return p_position;	
}

void movetonewposition(int position , int i, int j)
{
	//printf("\nIn Function move to new position\n");
	int ret ;
	
	if(position ==	1 )	{	next_grid_snap[i-1][j-1] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 2)	{	next_grid_snap[i-1][j] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 3)	{	next_grid_snap[i-1][j+1] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 4)	{	next_grid_snap[i][j+1] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 5)	{	next_grid_snap[i+1][j+1] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 6)	{	next_grid_snap[i-1][j] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 7)	{	next_grid_snap[i+1][j-1] = 1;	next_grid_snap[i][j] = 0 ;}
	else if(position == 8)	{	next_grid_snap[i][j-1] = 1;	next_grid_snap[i][j] = 0 ;}
	
	//printnext();
	initializegridbot();
	numberbots();
	//printnumberedbot();
	clearadjacencymatrix();
	createadjacencylist();
	//printf("\n\n\nAdjacency Matrix of  next snap : \n\n");
	//printad();
	//printf("\n\n");
	ret = chkconnectivity();
	
	//printf("Return Value from connectivity function: %d\n",ret);
	if(ret == 1) 
		{ 
                        
			//printf("Bots are connected to base station \n");
			
			if(position ==	1 )	{	grid[i-1][j-1] = 1;	grid[i][j] = 0; visited[i-1][j-1] += 1 ;}
			else if(position == 2)	{	grid[i-1][j] = 1;	grid[i][j] = 0; visited[i-1][j] += 1 ;}
			else if(position == 3)	{	grid[i-1][j+1] = 1;	grid[i][j] = 0; visited[i-1][j+1] += 1 ;}
			else if(position == 4)	{	grid[i][j+1] = 1;	grid[i][j] = 0; visited[i][j+1] += 1 ;}
			else if(position == 5)	{	grid[i+1][j+1] = 1;	grid[i][j] = 0; visited[i+1][j+1] += 1 ;}
			else if(position == 6)	{	grid[i-1][j] = 1;	grid[i][j] = 0; visited[i-1][j] += 1 ;}
			else if(position == 7)	{	grid[i+1][j-1] = 1;	grid[i][j] = 0; visited[i+1][j-1] += 1 ;}
			else if(position == 8)	{	grid[i][j-1] = 1;	grid[i][j] = 0; visited[i][j-1] += 1 ;}
                        print();
                        //printnumberedbot();
                        			
		}
	else	{
			//printf("Not Connected . Another Bot chosen for movement\n ");
			if(position ==	1 )	{	next_grid_snap[i-1][j-1] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 2)	{	next_grid_snap[i-1][j] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 3)	{	next_grid_snap[i-1][j+1] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 4)	{	next_grid_snap[i][j+1] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 5)	{	next_grid_snap[i+1][j+1] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 6)	{	next_grid_snap[i-1][j] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 7)	{	next_grid_snap[i+1][j-1] = 0;	next_grid_snap[i][j] = 1 ;}
			else if(position == 8)	{	next_grid_snap[i][j-1] = 0;	next_grid_snap[i][j] = 1 ;}

		}
}

void createadjacencylist()
{
	int i;
	int j;
	
	for(i=0 ; i<10 ; i++)
	{
		for(j=0 ; j<10 ;j++)
		{
			if(next_grid_snap[i][j] == 1)
			{
				chkneighbours(i,j,gridwithbotno[i][j]);
			}
		}
	}

}

void chkneighbours(int i , int j , int botnum)
{
	if((i-1)>=0 && (j-1)>=0 && (gridwithbotno[i-1][j-1] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i-1][j-1]-1] = 1;
		
	}
	if((i-1)>=0 && (j)>=0 && (gridwithbotno[i-1][j] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i-1][j]-1] = 1;
		
	}
	if((i-1)>=0 && (j+1)< 10 && (gridwithbotno[i-1][j+1] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i-1][j+1]-1] = 1;		
		
	}
	if((i)>=0 && (j+1)<10 && (gridwithbotno[i][j+1] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i][j+1]-1] = 1;		
		
	}
	if((i+1)<10 && (j+1)<10 && (gridwithbotno[i+1][j+1] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i+1][j+1]-1] = 1;
		
	}
	if((i+1)<10 && (j)>=0 && (gridwithbotno[i+1][j] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i+1][j]-1] = 1;
		
	}
	if((i+1)<10 && (j-1)>=0 && (gridwithbotno[i+1][j-1] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i+1][j-1]-1] = 1;
		
	}
	if((i)>=0 && (j-1)>=0 && (gridwithbotno[i][j-1] > 0))
	{
		admatrix[botnum-1][gridwithbotno[i][j-1]-1] = 1;
	}
}

int chkconnectivity()
{
	int i,j;
	for(i =0 ; i<26 ;i++) { bot[i] = 0; }
	basestation= gridwithbotno[5][4];
	int count =0;
	
	//printf("Base Station : %d\n",basestation);
	connected(basestation-1);
	
	for(j =0 ; j<26 ;j++ )
	{
		if(bot[j] == 1) count++;
		
	}
	
	/*for(j =0 ; j<26 ; j++)
	{
		if(bot[j] == 1)
		printf(" %d", j);
	}*/
	
	if(count == 25)
	{
		//printf("\n All bots connected to base station \n"); 
		return 1;
	}else 
		{
			//printf("\n Not connected\n"); 
			return 0;
		}	
}

void connected(int startpoint)
{
	int j;
		for (j=0 ; j< 26 ;j++ )
		{
			if( admatrix[startpoint][j] == 1)
			{
				if(j == (basestation-1) || bot[j] == 1){continue ;}
				bot[j] = 1; //printf("\n%d", j);
				connected(j);
			}
		} 
}

void numberbots()
{
	int i,j;
	int k = 1; // for bot numbers

	for(i =0 ; i< 10 ;i++)
	{
		for(j =0 ; j< 10 ;j++)
		{
			if(next_grid_snap[i][j] == 1)
			{
				gridwithbotno[i][j] = k;
				k++;
			}
		}
	}

}

void print()		// printing grid positions
{
	//printf("\n Current Bot Positions \n");
	int i;
	int j;
	for(i=0; i<10 ;i++)
	{
		for(j=0; j<10;j++)
		{
			if(i == 5 && j == 4)
			{
				printf("+   ");
			}else
				{
				printf("%d   ",grid[i][j]);
				}
		}
		printf("\n");
	}
}

void printnext()	// printing next grid position
{
	//printf("\nNext Bot Positions if bot moves \n");
	int i;
	int j;
	for(i=0; i<10 ;i++)
	{
		for(j=0; j<10;j++)
		{
			printf("%d   ",next_grid_snap[i][j]);
		}
		printf("\n");
	}
}

void printnumberedbot()		// printing grid with bot number
{
	//printf("\nBots Numbered\n");
	int i;
	int j;
	for(i=0; i<10 ;i++)
	{
		for(j=0; j<10;j++)
		{
			printf("%d ",gridwithbotno[i][j]);
		}
		printf("\n");
	}
}

void printad()			// printing adjacency matrix
{
	int i;
	int j;
	for(i=0; i<26 ;i++)
	{
		printf("\n %d\t",i+1);
		for(j=0; j<26;j++)
		{
			printf("%d   ",admatrix[i][j]);
		}
		printf("\n");
	}

}

void initializegridbot()	// initialize grid with bot number matrix
{
	int i , j;
	for(i =0 ; i<10 ;i++)
	{
		for(j =0 ; j<10 ; j++)
		{
			gridwithbotno[i][j] = 0;
		}
	}
	
}

void initializebotpositions()
{
	grid[5][4] = 1;
	grid[0][2] = 1;	
	grid[1][1] = 1;	grid[1][6] = 1; grid[1][8] = 1;
	grid[2][2] = 1;	grid[4][5] = 1;	grid[2][7] = 1;
 	grid[2][5] = 1;	grid[5][6] = 1; grid[5][1] = 1;
	grid[3][3] = 1;	grid[6][2] = 1; grid[5][3] = 1;
	grid[3][6] = 1;	grid[6][5] = 1; grid[5][8] = 1;
	grid[4][2] = 1;	grid[7][2] = 1; grid[6][7] = 1;
	grid[4][4] = 1;	grid[7][6] = 1; grid[8][1] = 1;
	grid[8][5] = 1;	grid[9][6] = 1; grid[9][2] = 1;
	
	next_grid_snap[5][4] = 1;
	next_grid_snap[0][2] = 1;	
	next_grid_snap[1][1] = 1;	next_grid_snap[1][6] = 1; next_grid_snap[1][8] = 1;
	next_grid_snap[2][2] = 1;	next_grid_snap[4][5] = 1; next_grid_snap[2][7] = 1;
 	next_grid_snap[2][5] = 1;	next_grid_snap[5][6] = 1; next_grid_snap[5][1] = 1;
	next_grid_snap[3][3] = 1;	next_grid_snap[6][2] = 1; next_grid_snap[5][3] = 1;
	next_grid_snap[3][6] = 1;	next_grid_snap[6][5] = 1; next_grid_snap[5][8] = 1;
	next_grid_snap[4][2] = 1;	next_grid_snap[7][2] = 1; next_grid_snap[6][7] = 1;
	next_grid_snap[4][4] = 1;	next_grid_snap[7][6] = 1; next_grid_snap[8][1] = 1;
	next_grid_snap[8][5] = 1;	next_grid_snap[9][6] = 1; next_grid_snap[9][2] = 1;
	
}

void clearadjacencymatrix()
{
	int i;
	int j;
	for(i=0; i<26 ;i++)
	{
		for(j=0; j<26;j++)
		{
			admatrix[i][j] = 0;
		}
	}
}

void initialize_visited_matrix()
{
	visited[5][4] = 1;
	visited[0][2] = 1;	
	visited[1][1] = 1;	visited[1][6] = 1; visited[1][8] = 1;
	visited[2][2] = 1;	visited[4][5] = 1; visited[2][7] = 1;
 	visited[2][5] = 1;	visited[5][6] = 1; visited[5][1] = 1;
	visited[3][3] = 1;	visited[6][2] = 1; visited[5][3] = 1;
	visited[3][6] = 1;	visited[6][5] = 1; visited[5][8] = 1;
	visited[4][2] = 1;	visited[7][2] = 1; visited[6][7] = 1;
	visited[4][4] = 1;	visited[7][6] = 1; visited[8][1] = 1;
	visited[8][5] = 1;	visited[9][6] = 1; visited[9][2] = 1;	
}

void printvisited()
{
	int i, j;
	for(i=0 ; i<10 ; i++)
	{
		for(j=0 ; j<10 ; j++)
		{
			printf("%d ",visited[i][j]);
		}
		printf("\n");
	}
}